# Prefix Sum

• 2026년 8월 6일 알고리즘
  추가 설명 — 왜 이어 붙이는 것이 최선인가

  최대 부분배열의 갱신식은 '앞부분의 최선은 kⱼ' 라는 한 줄을 당연하게 쓴다. 그 한 줄을 후보끼리의 1:1 대응으로 증명하고, 누적합에서 지금까지의 최소를 빼는 다른 풀이가 사실 같은 값을 계산한다는 것까지 보인다.

• 2026년 8월 6일 알고리즘
  최대 부분배열 — 자리마다 최선 하나만 들고 간다

  합이 가장 큰 연속 구간을 찾는 문제를 세 번 푼다. 모든 구간을 세면 O(N³), 누적합을 미리 만들면 O(N²), 각 자리에서 끝나는 최선의 합 하나만 들고 가면 O(N)이다. 빈 배열을 답으로 허용하느냐가 점화식을 어떻게 바꾸는지까지 본다.